package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class ConvertSortedListToBinarySearchTree {
    // 2023-02-08 16:57:15
    public static void main(String[] args) {
        Solution solution = new ConvertSortedListToBinarySearchTree().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        // 相当于链表的二分查找，即找中点，使用快慢指针
        public TreeNode sortedListToBST(ListNode head) {
            return dfs(head);
        }

        public TreeNode dfs(ListNode head) {
            if (head == null) return null;
            if (head.next == null) return new TreeNode(head.val);
            ListNode pre = new ListNode(0);
            pre.next = head;
            ListNode low = head, fast = head;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                low = low.next;
                pre = pre.next;
            }
            // pre 是low的前一个，此处是将前半部分从中点处断开
            pre.next = null;
            TreeNode root = new TreeNode(low.val);
            root.right = dfs(low.next);
            root.left = dfs(head);
            return root;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}